package main.LeetCode75.Level1;

import java.util.*;

public class Day11_Day15 {
    public static void main(String[] args) {
        System.out.println("**************************Day11**************************");
        System.out.println("Question746：使用最小花费爬楼梯");
        System.out.println("Question62：不同路径");
        System.out.println("**************************Day12**************************");
        System.out.println("Question438：找到字符串中所有字母异位词");
        System.out.println("Question424：替换后的最长重复字符");
        System.out.println("**************************Day13**************************");
        System.out.println("Question1：两数之和");
        System.out.println("Question299：猜数字游戏");
        System.out.println("**************************Day14**************************");
        System.out.println("Question844：比较含退格的字符串");
        System.out.println("Question394：字符串解码");
        System.out.println("**************************Day15**************************");
        System.out.println("Question1046：最后一块石头的重量");
        System.out.println("Question692：前K个高频单词");
    }
}

class Question746{
    public int minCostClimbingStairs(int[] cost) {
        int length=cost.length;//动态规划表
        int[] dp=new int[length];
        if (length==1) return cost[0];
        for (int i=0;i<length;i++){
            if (i==0||i==1) dp[i]=cost[i];
            else {
                dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i];
            }
        }
        return Math.min(dp[length-1],dp[length-2]);
    }
}

class Question62{
    public int process(int m,int n,int i,int j){//暴力递归动态规划
        if (i>=m||j>=n) return 0;
        if (i==m-1&&j==n-1) return 1;
        int right=process(m,n,i,j+1);
        int down=process(m,n,i+1,j);
        return right+down;
    }
    public int uniquePaths(int m, int n) {
//        return process(m,n,0,0);
        int[][] dp=new int[m][n];//动态规划表
        for (int i=0;i< dp.length;i++){
            for (int j=0;j<dp[0].length;j++){
                if (i==0||j==0) dp[i][j]=1;//0行0列为1
                else {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

class Question438{
    public boolean process(Map<Character,Integer> sMap, Map<Character,Integer> pMap){
        for (Character key:pMap.keySet()){
            if (!sMap.containsKey(key)||sMap.get(key)!=pMap.get(key))//若不存在或存在不相等
                return false;
        }
        return true;
    }
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) return new ArrayList<Integer>();
        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }
        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) ++differ;
        }
        if (differ == 0) ans.add(0);
        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s.charAt(i) - 'a'] == 1) --differ;// 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
            else if (count[s.charAt(i) - 'a'] == 0) ++differ;// 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
            --count[s.charAt(i) - 'a'];
            if (count[s.charAt(i + pLen) - 'a'] == -1) --differ;// 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
            else if (count[s.charAt(i + pLen) - 'a'] == 0) ++differ;// 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
            ++count[s.charAt(i + pLen) - 'a'];
            if (differ == 0) ans.add(i + 1);
        }
        return ans;
    }
}

class Question424{
    public int characterReplacement(String s, int k) {
        int length=s.length();
        if (length<2) return length;
        char[] str=s.toCharArray();
        int left=0,right=0,maxCount=0,result=0;
        int[] counts=new int[26];
        while (right<length){
            counts[str[right]-'A']++;
            maxCount=Math.max(maxCount,counts[str[right++]-'A']);
            if (right-left>maxCount+k){
                counts[str[left]-'A']--;
                left++;
            }
            result=Math.max(result,right-left);
        }
        return result;
    }
}

class Question1{
    public int[] twoSum(int[] nums, int target) {
        int[] index=new int[2];
        boolean flag=false;
        for (int i=0;i< nums.length;i++){
            for (int j=i+1;j< nums.length;j++){
                if (nums[i]+nums[j]==target){
                    flag=!flag;
                    index[0]=i;
                    index[1]=j;
                    break;
                }
            }
            if (flag) break;
        }
        return index;
    }
}

class Question299{
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int[] cntS = new int[10];
        int[] cntG = new int[10];
        for (int i = 0; i < secret.length(); ++i) {
            if (secret.charAt(i) == guess.charAt(i)) {
                ++bulls;
            } else {
                ++cntS[secret.charAt(i) - '0'];
                ++cntG[guess.charAt(i) - '0'];
            }
        }
        int cows = 0;
        for (int i = 0; i < 10; ++i) {
            cows += Math.min(cntS[i], cntG[i]);
        }
        return Integer.toString(bulls) + "A" + Integer.toString(cows) + "B";
    }
}

class Question844{
    public boolean backspaceCompare(String s, String t) {
        StringBuffer str1=new StringBuffer(),str2=new StringBuffer();
        char[] chars1=s.toCharArray(),chars2=t.toCharArray();
        for (int i=0;i<chars1.length;i++){
            if (str1.length()!=0&&chars1[i]=='#')
                str1.deleteCharAt(str1.length()-1);//删除最后一个
            if (chars1[i]!='#') str1.append(chars1[i]);
        }
        for (int i=0;i< chars2.length;i++){
            if (str2.length()!=0&&chars2[i]=='#')
                str2.deleteCharAt(str2.length()-1);
            if (chars2[i]!='#') str2.append(chars2[i]);
        }
        return str1.toString().equals(str2.toString());
    }
}

class Question394{
    public String[] process(char[] s,int start){//遇到'['进入下一层递归，遇到']'返回本层递归结果，并返回本层递归后的坐标
        StringBuffer num=new StringBuffer(),str=new StringBuffer();
        String[] ans=new String[2];//0存结束位置，1存结果字符串
        int i=start;
        for (;i<s.length;){
            if (s[i]>='0'&&s[i]<='9') num.append(s[i]);
            else if (s[i]=='['){//进入下一层递归
                String[] temp=process(s,i+1);
                int times=Integer.valueOf(num.toString());
                num.delete(0,num.length());//重新计数
                for (int time=0;time<times;time++) str.append(temp[1]);
                i=Integer.valueOf(temp[0]);//下层递归结束位置
            }else if (s[i]==']'){//结束当前层递归
                ans[0]=String.valueOf(i);
                ans[1]=str.toString();
                break;
            }else {
                str.append(s[i]);
            }
            i++;
        }
        ans[0]=String.valueOf(i);
        ans[1]=str.toString();
        return ans;
    }
    public String decodeString(String s) {
        char[] str=s.toCharArray();
        String[] result=process(str,0);
        return result[1];
    }
}

class Question1046{
    public int lastStoneWeight(int[] stones) {
        List<Integer> list=new ArrayList<>();
        for (int weight:stones) list.add(weight);
        while (list.size()>1){
            Collections.sort(list);
            int size=list.size();
            int first=list.get(size-1),second=list.get(size-2);
            list.remove(size-1);
            list.remove(size-2);
            if (first!=second){
                list.add(first-second);
            }
        }
        if (list.size()==0) return 0;
        else return list.get(0);
    }
}

class Question692{
    public List<String> topKFrequent(String[] words, int k) {
        int length=words.length,i=0;
        Map<String,Integer> map=new HashMap<>();
        for (String word:words) map.put(word,map.getOrDefault(word,0)+1);
        String[][] counts=new String[map.size()][2];
        for (String word:map.keySet()){
            counts[i][0]=String.valueOf(map.get(word));
            counts[i++][1]=word;
        }
        Arrays.sort(counts, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                if (!o1[0].equals(o2[0])) {
                    return Integer.valueOf(o1[0])-Integer.valueOf(o2[0]);
                }else {
                    char[] str1=o1[1].toCharArray(),str2=o2[1].toCharArray();
                    int j=0;
                    while (j<str1.length&&j< str2.length){
                        if (str1[j]!=str2[j]) return str2[j]-str1[j];
                        j++;
                    }
                    if (j<str1.length) return -1;
                    else return 1;
                }
            }
        });
        List<String> list=new ArrayList<>();
        for (int j=0;j<k;j++) list.add(counts[counts.length-1-j][1]);
        return list;
    }
}